/*
    libnbds
    Non-blocking Data Structures Library

    Copyright (C) 2011 Paweł Dziepak

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef NBDS_FIFO_H
#define NBDS_FIFO_H

#include "type.h"
#include "hazard_pointer.h"

namespace nbds {
	/* The Data Structure Itself (lock-free) */
	class fifo_base {
	private:
		struct elem {
			void *obj;
			elem *prev;
		};

		elem *first;
		elem *last;

		hazard_pointer<elem*> hp;

	protected:
		fifo_base() : first(0), last(0) { }

		void enqueue_(void *);
		void *dequeue_();

		bool is_empty_() {
			return !first;
		}
	};

	template<typename T, bool is_primitive>
	class fifo_wrapper;

	template<typename T>
	class fifo_wrapper<T, false> : public fifo_base {
	public:
		void enqueue(const T &x) {
			enqueue_(reinterpret_cast<void*>(new T(x)));
		}

		T dequeue() {
			T *x = reinterpret_cast<T*>(dequeue_());
			if (!x)
				return T();

			T obj = *x;
			delete x;

			return obj;
		}

		bool is_empty() {
			return is_empty_();
		}
	};

	template<typename T>
	class fifo_wrapper<T, true> : public fifo_base {
	public:
		void enqueue(const T &x) {
			enqueue_(reinterpret_cast<void*>(x));
		}

		T dequeue() {
			void *x = dequeue_();
			if (!x)
				return T();

			T obj = (T)((char*)x - (char*)0);

			return obj;
		}

		bool is_empty() {
			return is_empty_();
		}
	};

	template<typename T>
	class fifo : public fifo_wrapper<T, is_primitive<T>::value > { };
}

#endif
